W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Byteasar loves trekking in the hills. During the hikes he explores all the ridges and valleys in vicinity. Therefore, in order to plan the journey and know how long it will last, he must know the number of ridges and valleys in the area he is going to visit. And you are to help Byteasar.
Byteasar has provided you with a map of the area of his very next expedition. The map is in the shape of a square. For each field belonging to the square (for ), its height is given.
We say two fields are adjacent if they have a common side or a common vertex (i.e. the field is adjacent to the fields , , , , , , , , provided that these fields are on the map).
We say a set of fields forms a ridge (valley) if:
In particular, if all the fields on the map have the same height, they form both a ridge and a valley.
Your task is to determine the number of ridges and valleys for the landscape described by the map.
Write a programme that:
In the first line of the standard input there is one integer () denoting the size of the map. In each of the following lines there is the description of the successive row of the map. In 'th line (for ) there are integers , ..., (), separated by single spaces. These denote the heights of the successive fields of the 'th row of the map.
The first and only line of the standard output should contain two integers separated by a single space - the number of ridges followed by the number of valleys for the landscape described by the map.
For the input data:
5 8 8 8 7 7 7 7 8 8 7 7 7 7 7 7 7 8 8 7 8 7 8 8 8 8
the correct result is:
2 1
while for the input data:
5 5 7 8 3 1 5 5 7 6 6 6 6 6 2 8 5 7 2 5 8 7 1 0 1 7
the correct result is:
3 3
The above figures show the ridges (continuous line) and the valleys (dashed line).
Task author: Zbigniew Czech.